#include <stdio.h>
#include <stdlib.h>

#include "board.h"
#include "constants.h"
#include "utilities.h"

// Stack of allocated but unused grids
grid * unused_grids = NULL;

// print horizontal rule
void print_grid_hr(int columns, int width)
{
	int i;
	for (; columns != 0; columns--)
	{
		putchar('+');
		for (i = width; i != 0; i--)
			putchar('-');
	}
	putchar('+');
	putchar('\n');
}

void print_grid_empty(int columns, int width)
{
	int i;
	for (; columns != 0; columns--)
	{
		putchar('|');
		for (i = width; i != 0; i--)
			putchar(' ');
	}
	putchar('|');
	putchar('\n');
}

// pad the cell with spaces
int print_grid_pad(int n, int width)
{
	int i = 1;
	while ((n /= 10) != 0) i++;
	return (i = width - i) < 0 ? 0 : (i + 1) >> 1;
}

grid* create_grid(int rows, int columns)
{
	grid *g;
	int i;

#ifdef SAFE
	if (rows <= 0 || columns <= 0) return NULL;
#endif

	g = (grid*)malloc(sizeof(grid));
#ifdef SAFE
	if (NULL == g) return NULL;
#endif

	g -> rows = rows;
	g -> columns = columns;
    g -> length = rows * columns;
	g -> array = (int*)malloc(sizeof(int) * rows * columns);
#ifdef SAFE
	if (NULL == g -> array)
	{
		free(g);
		return NULL;
	}
#endif

	g -> grid = (int**)malloc(sizeof(int*) * rows);
#ifdef SAFE
	if (NULL == g -> grid)
	{
		free(g -> array);
		free(g);
		return NULL;
	}
#endif

	for (i = 0; i < rows; i++)
		g -> grid[i] = g -> array + i * columns;

	return g;
}

grid* pop_grid()
{
    if (unused_grids == NULL) return create_grid(GRID_ROWS, GRID_COLUMNS);
    grid * ret = unused_grids;
    unused_grids = unused_grids -> next;
    return ret;
}

void push_grid(grid *g)
{
	g -> next = unused_grids;
	unused_grids = g;
}

void init_grid(grid *g)
{
	int i, j;
	for (i = 0; i < g -> rows; i++)
		for (j = 0; j < g -> columns; j++)
			g -> grid[i][j] = 0;
}

void destroy_grid(grid *g)
{
	free(g -> array);
	free(g -> grid);
	free(g);
}

void cleanup_unused_grids()
{
    while (unused_grids != NULL)
    {
        grid * cur = unused_grids -> next;
        destroy_grid(unused_grids);
        unused_grids = cur;
    }
}

void copy_into(grid *from, grid *to)
{
    if (from == NULL || to == NULL) {
printf("from is not null? %d\n", from != NULL);
printf("to is not null? %d\n", to != NULL);
    }
	int i, j;
	to -> rows = from -> rows;
	to -> columns = from -> columns;
	for (i = 0; i < to -> rows; i++)
		for (j = 0; j < to -> columns; j++)
			to -> grid[i][j] = from -> grid[i][j];
}

grid* copy(grid *g)
{
	grid *h;
	h = create_grid(g -> rows, g -> columns);
#ifdef SAFE
	if (NULL == h) return NULL;
#endif
	copy_into(g, h);
	return h;
}

void print_grid(grid *g, int width, int height)
{
	int i, j, r, k, m, n;

	r = height >> 1;
	for (i = 0; i < g -> rows; i++)
	{
		print_grid_hr(g -> columns, width);
		for (j = 0; j < r; j++)
			print_grid_empty(g -> columns, width);

		for (k = 0; k < g -> columns; k++)
		{
			if (0 == g -> grid[i][k])
			{
				putchar('|');
				for (m = 0; m < width; m++)
					putchar(' ');
			}
			else
			{
                int val = 1 << g -> grid[i][k];
				printf("|%*s%d%n",
						print_grid_pad(val, width), "",
						val,
						&n);
				n = max(0, width + 1 - n);
				while (n-- != 0)
					putchar(' ');
			}
		}
		putchar('|');
		putchar('\n');

		for (j++; j < height; j++)
			print_grid_empty(g -> columns, width);
	}
	print_grid_hr(g -> columns, width);
}

void move_left(grid *g)
{
    int i,j,c;
    for (i = 0; i < g -> rows; ++i)
    {
        c = 0;
        for (j = 1; j < g -> columns; ++j)
        {
            int k = g -> grid[i][j];
            if (k > 0) 
            {
                if (g -> grid[i][c] == k) 
                {
                    ++g -> grid[i][c];
                    g -> grid[i][j] = 0;
                    ++c; // cannot increment again
                } 
                else if (g -> grid[i][c] == 0)
                {
                    g -> grid[i][j] = 0;
                    g -> grid[i][c] = k;
                } 
                else 
                {
                    ++c;
                    g -> grid[i][j] = 0;
                    g -> grid[i][c] = k;
                }
            }
        }
    }
}

void move_right(grid *g)
{
    int i,j,c;
    for (i = 0; i < g -> rows; ++i)
    {
        c = g -> columns-1;
         for (j = c-1; j >= 0; --j)
         {
            int k = g -> grid[i][j];
            if (k > 0) 
            {
                if (g -> grid[i][c] == k) 
                {
                    ++g -> grid[i][c];
                    g -> grid[i][j] = 0;
                    --c; // cannot increment again
                } 
                else if (g -> grid[i][c] == 0)
                {
                    g -> grid[i][j] = 0;
                    g -> grid[i][c] = k;
                } 
                else 
                {
                    --c;
                    g -> grid[i][j] = 0;
                    g -> grid[i][c] = k;
                }
            }
        }
    }
}

void move_up(grid *g)
{
    int i,j,r;
    for (j = 0; j < g -> columns; ++j)
    {
        r = 0;
        for (i = 1; i < g -> rows; ++i)
        {
            int k = g -> grid[i][j];
            if (k > 0) 
            {
                if (g -> grid[r][j] == k) 
                {
                    ++g -> grid[r][j];
                    g -> grid[i][j] = 0;
                    ++r; // cannot increment again
                } 
                else if (g -> grid[r][j] == 0)
                {
                    g -> grid[r][j] = k;
                    g -> grid[i][j] = 0;
                } 
                else 
                {
                    ++r;
                    g -> grid[i][j] = 0;
                    g -> grid[r][j] = k;
                }
            }
        }
    }
}

void move_down(grid *g)
{
    int i,j,r;
    for (j = 0; j < g -> columns; ++j)
    {
        r = g -> rows-1;
        for (i = r-1; i >= 0; --i)
        {
            int k = g -> grid[i][j];
            if (k > 0) 
            {
                if (g -> grid[r][j] == k) 
                {
                    ++g -> grid[r][j];
                    g -> grid[i][j] = 0;
                    --r; // cannot increment again
                } 
                else if (g -> grid[r][j] == 0)
                {
                    g -> grid[i][j] = 0;
                    g -> grid[r][j] = k;
                } 
                else 
                {
                    --r;
                    g -> grid[i][j] = 0;
                    g -> grid[r][j] = k;
                }
            }
        }
    }
}

int smoothness1(grid *g)
{
	int i, j;
	int cur;
	int s = 0;
	for (i = 0; i < g -> rows; i++)
	{
		for (j = 0; j < g -> columns && 0 == g -> grid[i][j]; j++);
		if (j >= g -> columns) continue;
		cur = g -> grid[i][j];
		for (j++; j < g -> columns; j++)
		{
			if (0 == g -> grid[i][j]) continue;
			s += abs(cur - g -> grid[i][j]);
			cur = g -> grid[i][j];
		}
	}
	for (j = 0; j < g -> columns; j++)
	{
		for (i = 0; i < g -> rows && 0 == g -> grid[i][j]; i++);
		if (i >= g -> rows) continue;
		cur = g -> grid[i][j];
		for (i++; i < g -> rows; i++)
		{
			if (0 == g -> grid[i][j]) continue;
			s += abs(cur - g -> grid[i][j]);
			cur = g -> grid[i][j];
		}
	}
	return s;
}

int monotonicity1(grid *g)
{
	int i, j;
	int d, e, cur;
	int m = 0;
	for (i = 0; i < g -> rows; i++)
	{
		d = 0;
		for (j = 0; j < g -> columns && 0 == g -> grid[i][j]; j++);
		if (j >= g -> columns) continue;
		cur = g -> grid[i][j];
		while (TRUE)
		{
			for (j++; j < g -> columns && 0 == g -> grid[i][j]; j++);
			if (j >= g -> columns) break;
			e = sgn(cur - g -> grid[i][j]);
			cur = g -> grid[i][j];
			if (!(d && e)) // at least one of d, e is 0
			{
				d += e; // discard one 0
				// monotone
			}
			else if (d != e) // +1, -1
			{
				d = e;
				m++;
			}
		}
	}
	for (j = 0; j < g -> columns; j++)
	{
		d = 0;
		for (i = 0; i < g -> rows && 0 == g -> grid[i][j]; i++);
		if (i >= g -> rows) continue;
		cur = g -> grid[i][j];
		while (TRUE)
		{
			for (i++; i < g -> rows && 0 == g -> grid[i][j]; i++);
			if (i >= g -> rows) break;
			e = sgn(cur - g -> grid[i][j]);
			cur = g -> grid[i][j];
			if (!(d && e)) // at least one of d, e is 0
			{
				d += e; // discard one 0
				// monotone
			}
			else if (d != e) // +1, -1
			{
				d = e;
				m++;
			}
		}
	}
	return m;
}
int empty_count(grid *g)
{
	int i;
	int e = 0;
	for (i = 0; i < g -> length; i++)
		e += (0 == g -> array[i]);
	return e;
}

int max_value(grid *g)
{
	int i, m;
	for (m = i = 0; i < g -> length; i++)
		m = max(m, g -> array[i]);
	return m;
}
